1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.cache;
18
19 import static com.google.common.cache.CacheBuilder.NULL_TICKER;
20 import static com.google.common.cache.LocalCache.DISCARDING_QUEUE;
21 import static com.google.common.cache.LocalCache.DRAIN_THRESHOLD;
22 import static com.google.common.cache.LocalCache.nullEntry;
23 import static com.google.common.cache.LocalCache.unset;
24 import static com.google.common.cache.TestingCacheLoaders.identityLoader;
25 import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener;
26 import static com.google.common.cache.TestingRemovalListeners.queuingRemovalListener;
27 import static com.google.common.cache.TestingWeighers.constantWeigher;
28 import static com.google.common.collect.Lists.newArrayList;
29 import static com.google.common.collect.Maps.immutableEntry;
30 import static java.util.concurrent.TimeUnit.MINUTES;
31 import static java.util.concurrent.TimeUnit.NANOSECONDS;
32 import static java.util.concurrent.TimeUnit.SECONDS;
33
34 import com.google.common.base.Equivalence;
35 import com.google.common.base.Ticker;
36 import com.google.common.cache.LocalCache.EntryFactory;
37 import com.google.common.cache.LocalCache.LoadingValueReference;
38 import com.google.common.cache.LocalCache.LocalLoadingCache;
39 import com.google.common.cache.LocalCache.LocalManualCache;
40 import com.google.common.cache.LocalCache.ReferenceEntry;
41 import com.google.common.cache.LocalCache.Segment;
42 import com.google.common.cache.LocalCache.Strength;
43 import com.google.common.cache.LocalCache.ValueReference;
44 import com.google.common.cache.TestingCacheLoaders.CountingLoader;
45 import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener;
46 import com.google.common.cache.TestingRemovalListeners.QueuingRemovalListener;
47 import com.google.common.collect.ImmutableList;
48 import com.google.common.collect.ImmutableMap;
49 import com.google.common.collect.ImmutableSet;
50 import com.google.common.collect.Lists;
51 import com.google.common.collect.Maps;
52 import com.google.common.collect.testing.MapTestSuiteBuilder;
53 import com.google.common.collect.testing.TestStringMapGenerator;
54 import com.google.common.collect.testing.features.CollectionFeature;
55 import com.google.common.collect.testing.features.CollectionSize;
56 import com.google.common.collect.testing.features.MapFeature;
57 import com.google.common.testing.FakeTicker;
58 import com.google.common.testing.NullPointerTester;
59 import com.google.common.testing.SerializableTester;
60 import com.google.common.testing.TestLogHandler;
61
62 import junit.framework.Test;
63 import junit.framework.TestCase;
64 import junit.framework.TestSuite;
65
66 import java.io.Serializable;
67 import java.lang.ref.Reference;
68 import java.lang.ref.ReferenceQueue;
69 import java.util.Iterator;
70 import java.util.LinkedHashMap;
71 import java.util.List;
72 import java.util.Map;
73 import java.util.Map.Entry;
74 import java.util.Random;
75 import java.util.Set;
76 import java.util.concurrent.CountDownLatch;
77 import java.util.concurrent.ExecutionException;
78 import java.util.concurrent.TimeUnit;
79 import java.util.concurrent.atomic.AtomicReferenceArray;
80 import java.util.logging.LogRecord;
81
82
83
84
85 public class LocalCacheTest extends TestCase {
86
87 public static Test suite() {
88 TestSuite suite = new TestSuite();
89 suite.addTestSuite(LocalCacheTest.class);
90 suite.addTest(MapTestSuiteBuilder.using(new TestStringMapGenerator() {
91 @Override public Map<String, String> create(
92 Entry<String, String>[] entries) {
93 LocalCache<String, String> map = makeLocalCache(createCacheBuilder());
94 for (Entry<String, String> entry : entries) {
95 map.put(entry.getKey(), entry.getValue());
96 }
97 return map;
98 }
99
100 }).named("LocalCache with defaults")
101 .withFeatures(CollectionSize.ANY, MapFeature.GENERAL_PURPOSE,
102 CollectionFeature.SUPPORTS_ITERATOR_REMOVE)
103 .createTestSuite());
104 return suite;
105 }
106
107 static final int SMALL_MAX_SIZE = DRAIN_THRESHOLD * 5;
108
109 TestLogHandler logHandler;
110
111 @Override
112 public void setUp() throws Exception {
113 super.setUp();
114 logHandler = new TestLogHandler();
115 LocalCache.logger.addHandler(logHandler);
116 }
117
118 @Override
119 public void tearDown() throws Exception {
120 super.tearDown();
121 LocalCache.logger.removeHandler(logHandler);
122 }
123
124 private Throwable popLoggedThrowable() {
125 List<LogRecord> logRecords = logHandler.getStoredLogRecords();
126 assertSame(1, logRecords.size());
127 LogRecord logRecord = logRecords.get(0);
128 logHandler.clear();
129 return logRecord.getThrown();
130 }
131
132 private void checkNothingLogged() {
133 assertTrue(logHandler.getStoredLogRecords().isEmpty());
134 }
135
136 private void checkLogged(Throwable t) {
137 assertSame(t, popLoggedThrowable());
138 }
139
140 private static <K, V> LocalCache<K, V> makeLocalCache(
141 CacheBuilder<? super K, ? super V> builder) {
142 return new LocalCache<K, V>(builder, null);
143 }
144
145 private static CacheBuilder<Object, Object> createCacheBuilder() {
146 return new CacheBuilder<Object, Object>();
147 }
148
149
150
151 public void testDefaults() {
152 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
153
154 assertSame(Strength.STRONG, map.keyStrength);
155 assertSame(Strength.STRONG, map.valueStrength);
156 assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
157 assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
158
159 assertEquals(0, map.expireAfterAccessNanos);
160 assertEquals(0, map.expireAfterWriteNanos);
161 assertEquals(0, map.refreshNanos);
162 assertEquals(CacheBuilder.UNSET_INT, map.maxWeight);
163
164 assertSame(EntryFactory.STRONG, map.entryFactory);
165 assertSame(CacheBuilder.NullListener.INSTANCE, map.removalListener);
166 assertSame(DISCARDING_QUEUE, map.removalNotificationQueue);
167 assertSame(NULL_TICKER, map.ticker);
168
169 assertEquals(4, map.concurrencyLevel);
170
171
172 assertEquals(4, map.segments.length);
173
174 assertEquals(16 / map.segments.length, map.segments[0].table.length());
175
176 assertFalse(map.evictsBySize());
177 assertFalse(map.expires());
178 assertFalse(map.expiresAfterWrite());
179 assertFalse(map.expiresAfterAccess());
180 assertFalse(map.refreshes());
181 }
182
183 public void testSetKeyEquivalence() {
184 Equivalence<Object> testEquivalence = new Equivalence<Object>() {
185 @Override
186 protected boolean doEquivalent(Object a, Object b) {
187 return false;
188 }
189
190 @Override
191 protected int doHash(Object t) {
192 return 0;
193 }
194 };
195
196 LocalCache<Object, Object> map =
197 makeLocalCache(createCacheBuilder().keyEquivalence(testEquivalence));
198 assertSame(testEquivalence, map.keyEquivalence);
199 assertSame(map.valueStrength.defaultEquivalence(), map.valueEquivalence);
200 }
201
202 public void testSetValueEquivalence() {
203 Equivalence<Object> testEquivalence = new Equivalence<Object>() {
204 @Override
205 protected boolean doEquivalent(Object a, Object b) {
206 return false;
207 }
208
209 @Override
210 protected int doHash(Object t) {
211 return 0;
212 }
213 };
214
215 LocalCache<Object, Object> map =
216 makeLocalCache(createCacheBuilder().valueEquivalence(testEquivalence));
217 assertSame(testEquivalence, map.valueEquivalence);
218 assertSame(map.keyStrength.defaultEquivalence(), map.keyEquivalence);
219 }
220
221 public void testSetConcurrencyLevel() {
222
223
224 checkConcurrencyLevel(1, 1);
225 checkConcurrencyLevel(2, 2);
226 checkConcurrencyLevel(3, 4);
227 checkConcurrencyLevel(4, 4);
228 checkConcurrencyLevel(5, 8);
229 checkConcurrencyLevel(6, 8);
230 checkConcurrencyLevel(7, 8);
231 checkConcurrencyLevel(8, 8);
232 }
233
234 private static void checkConcurrencyLevel(int concurrencyLevel, int segmentCount) {
235 LocalCache<Object, Object> map =
236 makeLocalCache(createCacheBuilder().concurrencyLevel(concurrencyLevel));
237 assertEquals(segmentCount, map.segments.length);
238 }
239
240 public void testSetInitialCapacity() {
241
242
243 checkInitialCapacity(1, 0, 1);
244 checkInitialCapacity(1, 1, 1);
245 checkInitialCapacity(1, 2, 2);
246 checkInitialCapacity(1, 3, 4);
247 checkInitialCapacity(1, 4, 4);
248 checkInitialCapacity(1, 5, 8);
249 checkInitialCapacity(1, 6, 8);
250 checkInitialCapacity(1, 7, 8);
251 checkInitialCapacity(1, 8, 8);
252
253 checkInitialCapacity(2, 0, 1);
254 checkInitialCapacity(2, 1, 1);
255 checkInitialCapacity(2, 2, 1);
256 checkInitialCapacity(2, 3, 2);
257 checkInitialCapacity(2, 4, 2);
258 checkInitialCapacity(2, 5, 4);
259 checkInitialCapacity(2, 6, 4);
260 checkInitialCapacity(2, 7, 4);
261 checkInitialCapacity(2, 8, 4);
262
263 checkInitialCapacity(4, 0, 1);
264 checkInitialCapacity(4, 1, 1);
265 checkInitialCapacity(4, 2, 1);
266 checkInitialCapacity(4, 3, 1);
267 checkInitialCapacity(4, 4, 1);
268 checkInitialCapacity(4, 5, 2);
269 checkInitialCapacity(4, 6, 2);
270 checkInitialCapacity(4, 7, 2);
271 checkInitialCapacity(4, 8, 2);
272 }
273
274 private static void checkInitialCapacity(
275 int concurrencyLevel, int initialCapacity, int segmentSize) {
276 LocalCache<Object, Object> map = makeLocalCache(
277 createCacheBuilder().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity));
278 for (int i = 0; i < map.segments.length; i++) {
279 assertEquals(segmentSize, map.segments[i].table.length());
280 }
281 }
282
283 public void testSetMaximumSize() {
284
285
286 for (int maxSize = 1; maxSize < 100; maxSize++) {
287 checkMaximumSize(1, 8, maxSize);
288 checkMaximumSize(2, 8, maxSize);
289 checkMaximumSize(4, 8, maxSize);
290 checkMaximumSize(8, 8, maxSize);
291 }
292
293 checkMaximumSize(1, 8, Long.MAX_VALUE);
294 checkMaximumSize(2, 8, Long.MAX_VALUE);
295 checkMaximumSize(4, 8, Long.MAX_VALUE);
296 checkMaximumSize(8, 8, Long.MAX_VALUE);
297
298
299
300 for (int capacity = 0; capacity < 8; capacity++) {
301 checkMaximumSize(1, capacity, 4);
302 checkMaximumSize(2, capacity, 4);
303 checkMaximumSize(4, capacity, 4);
304 checkMaximumSize(8, capacity, 4);
305 }
306 }
307
308 private static void checkMaximumSize(int concurrencyLevel, int initialCapacity, long maxSize) {
309 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
310 .concurrencyLevel(concurrencyLevel)
311 .initialCapacity(initialCapacity)
312 .maximumSize(maxSize));
313 long totalCapacity = 0;
314 assertTrue("segments=" + map.segments.length + ", maxSize=" + maxSize,
315 map.segments.length <= Math.max(1, maxSize / 10));
316 for (int i = 0; i < map.segments.length; i++) {
317 totalCapacity += map.segments[i].maxSegmentWeight;
318 }
319 assertTrue("totalCapacity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity == maxSize);
320
321 map = makeLocalCache(createCacheBuilder()
322 .concurrencyLevel(concurrencyLevel)
323 .initialCapacity(initialCapacity)
324 .maximumWeight(maxSize)
325 .weigher(constantWeigher(1)));
326 assertTrue("segments=" + map.segments.length + ", maxSize=" + maxSize,
327 map.segments.length <= Math.max(1, maxSize / 10));
328 totalCapacity = 0;
329 for (int i = 0; i < map.segments.length; i++) {
330 totalCapacity += map.segments[i].maxSegmentWeight;
331 }
332 assertTrue("totalCapacity=" + totalCapacity + ", maxSize=" + maxSize, totalCapacity == maxSize);
333 }
334
335 public void testSetWeigher() {
336 Weigher<Object, Object> testWeigher = new Weigher<Object, Object>() {
337 @Override
338 public int weigh(Object key, Object value) {
339 return 42;
340 }
341 };
342 LocalCache<Object, Object> map =
343 makeLocalCache(createCacheBuilder().maximumWeight(1).weigher(testWeigher));
344 assertSame(testWeigher, map.weigher);
345 }
346
347 public void testSetWeakKeys() {
348 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().weakKeys());
349 checkStrength(map, Strength.WEAK, Strength.STRONG);
350 assertSame(EntryFactory.WEAK, map.entryFactory);
351 }
352
353 public void testSetWeakValues() {
354 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().weakValues());
355 checkStrength(map, Strength.STRONG, Strength.WEAK);
356 assertSame(EntryFactory.STRONG, map.entryFactory);
357 }
358
359 public void testSetSoftValues() {
360 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().softValues());
361 checkStrength(map, Strength.STRONG, Strength.SOFT);
362 assertSame(EntryFactory.STRONG, map.entryFactory);
363 }
364
365 private static void checkStrength(
366 LocalCache<Object, Object> map, Strength keyStrength, Strength valueStrength) {
367 assertSame(keyStrength, map.keyStrength);
368 assertSame(valueStrength, map.valueStrength);
369 assertSame(keyStrength.defaultEquivalence(), map.keyEquivalence);
370 assertSame(valueStrength.defaultEquivalence(), map.valueEquivalence);
371 }
372
373 public void testSetExpireAfterWrite() {
374 long duration = 42;
375 TimeUnit unit = TimeUnit.SECONDS;
376 LocalCache<Object, Object> map =
377 makeLocalCache(createCacheBuilder().expireAfterWrite(duration, unit));
378 assertEquals(unit.toNanos(duration), map.expireAfterWriteNanos);
379 }
380
381 public void testSetExpireAfterAccess() {
382 long duration = 42;
383 TimeUnit unit = TimeUnit.SECONDS;
384 LocalCache<Object, Object> map =
385 makeLocalCache(createCacheBuilder().expireAfterAccess(duration, unit));
386 assertEquals(unit.toNanos(duration), map.expireAfterAccessNanos);
387 }
388
389 public void testSetRefresh() {
390 long duration = 42;
391 TimeUnit unit = TimeUnit.SECONDS;
392 LocalCache<Object, Object> map =
393 makeLocalCache(createCacheBuilder().refreshAfterWrite(duration, unit));
394 assertEquals(unit.toNanos(duration), map.refreshNanos);
395 }
396
397 public void testSetRemovalListener() {
398 RemovalListener<Object, Object> testListener = TestingRemovalListeners.nullRemovalListener();
399 LocalCache<Object, Object> map =
400 makeLocalCache(createCacheBuilder().removalListener(testListener));
401 assertSame(testListener, map.removalListener);
402 }
403
404 public void testSetTicker() {
405 Ticker testTicker = new Ticker() {
406 @Override
407 public long read() {
408 return 0;
409 }
410 };
411 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().ticker(testTicker));
412 assertSame(testTicker, map.ticker);
413 }
414
415 public void testEntryFactory() {
416 assertSame(EntryFactory.STRONG,
417 EntryFactory.getFactory(Strength.STRONG, false, false));
418 assertSame(EntryFactory.STRONG_ACCESS,
419 EntryFactory.getFactory(Strength.STRONG, true, false));
420 assertSame(EntryFactory.STRONG_WRITE,
421 EntryFactory.getFactory(Strength.STRONG, false, true));
422 assertSame(EntryFactory.STRONG_ACCESS_WRITE,
423 EntryFactory.getFactory(Strength.STRONG, true, true));
424 assertSame(EntryFactory.WEAK,
425 EntryFactory.getFactory(Strength.WEAK, false, false));
426 assertSame(EntryFactory.WEAK_ACCESS,
427 EntryFactory.getFactory(Strength.WEAK, true, false));
428 assertSame(EntryFactory.WEAK_WRITE,
429 EntryFactory.getFactory(Strength.WEAK, false, true));
430 assertSame(EntryFactory.WEAK_ACCESS_WRITE,
431 EntryFactory.getFactory(Strength.WEAK, true, true));
432 }
433
434
435
436 public void testCompute() throws ExecutionException {
437 CountingLoader loader = new CountingLoader();
438 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
439 assertEquals(0, loader.getCount());
440
441 Object key = new Object();
442 Object value = map.get(key, loader);
443 assertEquals(1, loader.getCount());
444 assertEquals(value, map.get(key, loader));
445 assertEquals(1, loader.getCount());
446 }
447
448 public void testRecordReadOnCompute() throws ExecutionException {
449 CountingLoader loader = new CountingLoader();
450 for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
451 LocalCache<Object, Object> map =
452 makeLocalCache(builder.concurrencyLevel(1));
453 Segment<Object, Object> segment = map.segments[0];
454 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
455 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
456 for (int i = 0; i < SMALL_MAX_SIZE; i++) {
457 Object key = new Object();
458 int hash = map.hash(key);
459
460 map.get(key, loader);
461 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
462 writeOrder.add(entry);
463 readOrder.add(entry);
464 }
465
466 checkEvictionQueues(map, segment, readOrder, writeOrder);
467 checkExpirationTimes(map);
468 assertTrue(segment.recencyQueue.isEmpty());
469
470
471 Random random = new Random();
472 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
473 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
474 while (i.hasNext()) {
475 ReferenceEntry<Object, Object> entry = i.next();
476 if (random.nextBoolean()) {
477 map.get(entry.getKey(), loader);
478 reads.add(entry);
479 i.remove();
480 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
481 }
482 }
483 int undrainedIndex = reads.size() - segment.recencyQueue.size();
484 checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
485 readOrder.addAll(reads);
486
487 checkEvictionQueues(map, segment, readOrder, writeOrder);
488 checkExpirationTimes(map);
489 }
490 }
491
492 public void testComputeExistingEntry() throws ExecutionException {
493 CountingLoader loader = new CountingLoader();
494 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
495 assertEquals(0, loader.getCount());
496
497 Object key = new Object();
498 Object value = new Object();
499 map.put(key, value);
500
501 assertEquals(value, map.get(key, loader));
502 assertEquals(0, loader.getCount());
503 }
504
505 public void testComputePartiallyCollectedKey() throws ExecutionException {
506 CacheBuilder<Object, Object> builder = createCacheBuilder().concurrencyLevel(1);
507 CountingLoader loader = new CountingLoader();
508 LocalCache<Object, Object> map = makeLocalCache(builder);
509 Segment<Object, Object> segment = map.segments[0];
510 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
511 assertEquals(0, loader.getCount());
512
513 Object key = new Object();
514 int hash = map.hash(key);
515 Object value = new Object();
516 int index = hash & (table.length() - 1);
517
518 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
519 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value);
520 entry.setValueReference(valueRef);
521 table.set(index, entry);
522 segment.count++;
523
524 assertSame(value, map.get(key, loader));
525 assertEquals(0, loader.getCount());
526 assertEquals(1, segment.count);
527
528 entry.clearKey();
529 assertNotSame(value, map.get(key, loader));
530 assertEquals(1, loader.getCount());
531 assertEquals(2, segment.count);
532 }
533
534 public void testComputePartiallyCollectedValue() throws ExecutionException {
535 CacheBuilder<Object, Object> builder = createCacheBuilder().concurrencyLevel(1);
536 CountingLoader loader = new CountingLoader();
537 LocalCache<Object, Object> map = makeLocalCache(builder);
538 Segment<Object, Object> segment = map.segments[0];
539 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
540 assertEquals(0, loader.getCount());
541
542 Object key = new Object();
543 int hash = map.hash(key);
544 Object value = new Object();
545 int index = hash & (table.length() - 1);
546
547 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
548 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value);
549 entry.setValueReference(valueRef);
550 table.set(index, entry);
551 segment.count++;
552
553 assertSame(value, map.get(key, loader));
554 assertEquals(0, loader.getCount());
555 assertEquals(1, segment.count);
556
557 valueRef.clear();
558 assertNotSame(value, map.get(key, loader));
559 assertEquals(1, loader.getCount());
560 assertEquals(1, segment.count);
561 }
562
563 public void testComputeExpiredEntry() throws ExecutionException {
564 CacheBuilder<Object, Object> builder = createCacheBuilder()
565 .expireAfterWrite(1, TimeUnit.NANOSECONDS);
566 CountingLoader loader = new CountingLoader();
567 LocalCache<Object, Object> map = makeLocalCache(builder);
568 assertEquals(0, loader.getCount());
569
570 Object key = new Object();
571 Object one = map.get(key, loader);
572 assertEquals(1, loader.getCount());
573
574 Object two = map.get(key, loader);
575 assertNotSame(one, two);
576 assertEquals(2, loader.getCount());
577 }
578
579 public void testValues() {
580 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder());
581 map.put("foo", "bar");
582 map.put("baz", "bar");
583 map.put("quux", "quux");
584 assertFalse(map.values() instanceof Set);
585 assertTrue(map.values().removeAll(ImmutableSet.of("bar")));
586 assertEquals(1, map.size());
587 }
588
589 public void testCopyEntry_computing() {
590 final CountDownLatch startSignal = new CountDownLatch(1);
591 final CountDownLatch computingSignal = new CountDownLatch(1);
592 final CountDownLatch doneSignal = new CountDownLatch(2);
593 final Object computedObject = new Object();
594
595 final CacheLoader<Object, Object> loader = new CacheLoader<Object, Object>() {
596 @Override
597 public Object load(Object key) throws Exception {
598 computingSignal.countDown();
599 startSignal.await();
600 return computedObject;
601 }
602 };
603
604 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
605 CacheBuilder<Object, Object> builder = createCacheBuilder()
606 .concurrencyLevel(1)
607 .removalListener(listener);
608 final LocalCache<Object, Object> map = makeLocalCache(builder);
609 Segment<Object, Object> segment = map.segments[0];
610 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
611 assertTrue(listener.isEmpty());
612
613 final Object one = new Object();
614 int hash = map.hash(one);
615 int index = hash & (table.length() - 1);
616
617 new Thread() {
618 @Override
619 public void run() {
620 try {
621 map.get(one, loader);
622 } catch (ExecutionException e) {
623 throw new RuntimeException(e);
624 }
625 doneSignal.countDown();
626 }
627 }.start();
628
629 try {
630 computingSignal.await();
631 } catch (InterruptedException e) {
632 throw new RuntimeException(e);
633 }
634
635 new Thread() {
636 @Override
637 public void run() {
638 try {
639 map.get(one, loader);
640 } catch (ExecutionException e) {
641 throw new RuntimeException(e);
642 }
643 doneSignal.countDown();
644 }
645 }.start();
646
647 ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
648 ReferenceEntry<Object, Object> newEntry = segment.copyEntry(entry, null);
649 table.set(index, newEntry);
650
651 @SuppressWarnings("unchecked")
652 LoadingValueReference<Object, Object> valueReference =
653 (LoadingValueReference) newEntry.getValueReference();
654 assertFalse(valueReference.futureValue.isDone());
655 startSignal.countDown();
656
657 try {
658 doneSignal.await();
659 } catch (InterruptedException e) {
660 throw new RuntimeException(e);
661 }
662
663 map.cleanUp();
664 assertTrue(listener.isEmpty());
665 assertTrue(map.containsKey(one));
666 assertEquals(1, map.size());
667 assertSame(computedObject, map.get(one));
668 }
669
670 public void testRemovalListenerCheckedException() {
671 final RuntimeException e = new RuntimeException();
672 RemovalListener<Object, Object> listener = new RemovalListener<Object, Object>() {
673 @Override
674 public void onRemoval(RemovalNotification<Object, Object> notification) {
675 throw e;
676 }
677 };
678
679 CacheBuilder<Object, Object> builder = createCacheBuilder().removalListener(listener);
680 final LocalCache<Object, Object> cache = makeLocalCache(builder);
681 Object key = new Object();
682 cache.put(key, new Object());
683 checkNothingLogged();
684
685 cache.remove(key);
686 checkLogged(e);
687 }
688
689 public void testRemovalListener_replaced_computing() {
690 final CountDownLatch startSignal = new CountDownLatch(1);
691 final CountDownLatch computingSignal = new CountDownLatch(1);
692 final CountDownLatch doneSignal = new CountDownLatch(1);
693 final Object computedObject = new Object();
694
695 final CacheLoader<Object, Object> loader = new CacheLoader<Object, Object>() {
696 @Override
697 public Object load(Object key) throws Exception {
698 computingSignal.countDown();
699 startSignal.await();
700 return computedObject;
701 }
702 };
703
704 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
705 CacheBuilder<Object, Object> builder = createCacheBuilder().removalListener(listener);
706 final LocalCache<Object, Object> map = makeLocalCache(builder);
707 assertTrue(listener.isEmpty());
708
709 final Object one = new Object();
710 final Object two = new Object();
711
712 new Thread() {
713 @Override
714 public void run() {
715 try {
716 map.get(one, loader);
717 } catch (ExecutionException e) {
718 throw new RuntimeException(e);
719 }
720 doneSignal.countDown();
721 }
722 }.start();
723
724 try {
725 computingSignal.await();
726 } catch (InterruptedException e) {
727 throw new RuntimeException(e);
728 }
729
730 map.put(one, two);
731 assertSame(two, map.get(one));
732 startSignal.countDown();
733
734 try {
735 doneSignal.await();
736 } catch (InterruptedException e) {
737 throw new RuntimeException(e);
738 }
739
740 map.cleanUp();
741 assertNotified(listener, one, computedObject, RemovalCause.REPLACED);
742 assertTrue(listener.isEmpty());
743 }
744
745 public void testSegmentRefresh_duplicate() throws ExecutionException {
746 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
747 .concurrencyLevel(1));
748 Segment<Object, Object> segment = map.segments[0];
749
750 Object key = new Object();
751 int hash = map.hash(key);
752 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
753 int index = hash & (table.length() - 1);
754
755
756 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
757 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(null);
758 valueRef.setLoading(true);
759 entry.setValueReference(valueRef);
760 table.set(index, entry);
761 assertNull(segment.refresh(key, hash, identityLoader(), false));
762 }
763
764
765
766 public void testRemovalListener_explicit() {
767 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
768 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
769 .removalListener(listener));
770 assertTrue(listener.isEmpty());
771
772 Object one = new Object();
773 Object two = new Object();
774 Object three = new Object();
775 Object four = new Object();
776 Object five = new Object();
777 Object six = new Object();
778
779 map.put(one, two);
780 map.remove(one);
781 assertNotified(listener, one, two, RemovalCause.EXPLICIT);
782
783 map.put(two, three);
784 map.remove(two, three);
785 assertNotified(listener, two, three, RemovalCause.EXPLICIT);
786
787 map.put(three, four);
788 Iterator<?> i = map.entrySet().iterator();
789 i.next();
790 i.remove();
791 assertNotified(listener, three, four, RemovalCause.EXPLICIT);
792
793 map.put(four, five);
794 i = map.keySet().iterator();
795 i.next();
796 i.remove();
797 assertNotified(listener, four, five, RemovalCause.EXPLICIT);
798
799 map.put(five, six);
800 i = map.values().iterator();
801 i.next();
802 i.remove();
803 assertNotified(listener, five, six, RemovalCause.EXPLICIT);
804
805 assertTrue(listener.isEmpty());
806 }
807
808 public void testRemovalListener_replaced() {
809 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
810 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
811 .removalListener(listener));
812 assertTrue(listener.isEmpty());
813
814 Object one = new Object();
815 Object two = new Object();
816 Object three = new Object();
817 Object four = new Object();
818 Object five = new Object();
819 Object six = new Object();
820
821 map.put(one, two);
822 map.put(one, three);
823 assertNotified(listener, one, two, RemovalCause.REPLACED);
824
825 Map<Object, Object> newMap = ImmutableMap.of(one, four);
826 map.putAll(newMap);
827 assertNotified(listener, one, three, RemovalCause.REPLACED);
828
829 map.replace(one, five);
830 assertNotified(listener, one, four, RemovalCause.REPLACED);
831
832 map.replace(one, five, six);
833 assertNotified(listener, one, five, RemovalCause.REPLACED);
834 }
835
836 public void testRemovalListener_collected() {
837 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
838 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
839 .concurrencyLevel(1)
840 .softValues()
841 .removalListener(listener));
842 Segment<Object, Object> segment = map.segments[0];
843 assertTrue(listener.isEmpty());
844
845 Object one = new Object();
846 Object two = new Object();
847 Object three = new Object();
848
849 map.put(one, two);
850 map.put(two, three);
851 assertTrue(listener.isEmpty());
852
853 int hash = map.hash(one);
854 ReferenceEntry<Object, Object> entry = segment.getEntry(one, hash);
855 map.reclaimValue(entry.getValueReference());
856 assertNotified(listener, one, two, RemovalCause.COLLECTED);
857
858 assertTrue(listener.isEmpty());
859 }
860
861 public void testRemovalListener_expired() {
862 FakeTicker ticker = new FakeTicker();
863 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
864 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
865 .concurrencyLevel(1)
866 .expireAfterWrite(3, TimeUnit.NANOSECONDS)
867 .ticker(ticker)
868 .removalListener(listener));
869 assertTrue(listener.isEmpty());
870
871 Object one = new Object();
872 Object two = new Object();
873 Object three = new Object();
874 Object four = new Object();
875 Object five = new Object();
876
877 map.put(one, two);
878 ticker.advance(1);
879 map.put(two, three);
880 ticker.advance(1);
881 map.put(three, four);
882 assertTrue(listener.isEmpty());
883 ticker.advance(1);
884 map.put(four, five);
885 assertNotified(listener, one, two, RemovalCause.EXPIRED);
886
887 assertTrue(listener.isEmpty());
888 }
889
890 public void testRemovalListener_size() {
891 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
892 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
893 .concurrencyLevel(1)
894 .maximumSize(2)
895 .removalListener(listener));
896 assertTrue(listener.isEmpty());
897
898 Object one = new Object();
899 Object two = new Object();
900 Object three = new Object();
901 Object four = new Object();
902
903 map.put(one, two);
904 map.put(two, three);
905 assertTrue(listener.isEmpty());
906 map.put(three, four);
907 assertNotified(listener, one, two, RemovalCause.SIZE);
908
909 assertTrue(listener.isEmpty());
910 }
911
912 static <K, V> void assertNotified(
913 QueuingRemovalListener<K, V> listener, K key, V value, RemovalCause cause) {
914 RemovalNotification<K, V> notification = listener.remove();
915 assertSame(key, notification.getKey());
916 assertSame(value, notification.getValue());
917 assertSame(cause, notification.getCause());
918 }
919
920
921
922 public void testNewEntry() {
923 for (CacheBuilder<Object, Object> builder : allEntryTypeMakers()) {
924 LocalCache<Object, Object> map = makeLocalCache(builder);
925
926 Object keyOne = new Object();
927 Object valueOne = new Object();
928 int hashOne = map.hash(keyOne);
929 ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
930 ValueReference<Object, Object> valueRefOne = map.newValueReference(entryOne, valueOne, 1);
931 assertSame(valueOne, valueRefOne.get());
932 entryOne.setValueReference(valueRefOne);
933
934 assertSame(keyOne, entryOne.getKey());
935 assertEquals(hashOne, entryOne.getHash());
936 assertNull(entryOne.getNext());
937 assertSame(valueRefOne, entryOne.getValueReference());
938
939 Object keyTwo = new Object();
940 Object valueTwo = new Object();
941 int hashTwo = map.hash(keyTwo);
942 ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
943 ValueReference<Object, Object> valueRefTwo = map.newValueReference(entryTwo, valueTwo, 1);
944 assertSame(valueTwo, valueRefTwo.get());
945 entryTwo.setValueReference(valueRefTwo);
946
947 assertSame(keyTwo, entryTwo.getKey());
948 assertEquals(hashTwo, entryTwo.getHash());
949 assertSame(entryOne, entryTwo.getNext());
950 assertSame(valueRefTwo, entryTwo.getValueReference());
951 }
952 }
953
954 public void testCopyEntry() {
955 for (CacheBuilder<Object, Object> builder : allEntryTypeMakers()) {
956 LocalCache<Object, Object> map = makeLocalCache(builder);
957
958 Object keyOne = new Object();
959 Object valueOne = new Object();
960 int hashOne = map.hash(keyOne);
961 ReferenceEntry<Object, Object> entryOne = map.newEntry(keyOne, hashOne, null);
962 entryOne.setValueReference(map.newValueReference(entryOne, valueOne, 1));
963
964 Object keyTwo = new Object();
965 Object valueTwo = new Object();
966 int hashTwo = map.hash(keyTwo);
967 ReferenceEntry<Object, Object> entryTwo = map.newEntry(keyTwo, hashTwo, entryOne);
968 entryTwo.setValueReference(map.newValueReference(entryTwo, valueTwo, 1));
969 if (map.usesAccessQueue()) {
970 LocalCache.connectAccessOrder(entryOne, entryTwo);
971 }
972 if (map.usesWriteQueue()) {
973 LocalCache.connectWriteOrder(entryOne, entryTwo);
974 }
975 assertConnected(map, entryOne, entryTwo);
976
977 ReferenceEntry<Object, Object> copyOne = map.copyEntry(entryOne, null);
978 assertSame(keyOne, entryOne.getKey());
979 assertEquals(hashOne, entryOne.getHash());
980 assertNull(entryOne.getNext());
981 assertSame(valueOne, copyOne.getValueReference().get());
982 assertConnected(map, copyOne, entryTwo);
983
984 ReferenceEntry<Object, Object> copyTwo = map.copyEntry(entryTwo, copyOne);
985 assertSame(keyTwo, copyTwo.getKey());
986 assertEquals(hashTwo, copyTwo.getHash());
987 assertSame(copyOne, copyTwo.getNext());
988 assertSame(valueTwo, copyTwo.getValueReference().get());
989 assertConnected(map, copyOne, copyTwo);
990 }
991 }
992
993 private static <K, V> void assertConnected(
994 LocalCache<K, V> map, ReferenceEntry<K, V> one, ReferenceEntry<K, V> two) {
995 if (map.usesWriteQueue()) {
996 assertSame(two, one.getNextInWriteQueue());
997 }
998 if (map.usesAccessQueue()) {
999 assertSame(two, one.getNextInAccessQueue());
1000 }
1001 }
1002
1003 public void testSegmentGetAndContains() {
1004 FakeTicker ticker = new FakeTicker();
1005 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1006 .concurrencyLevel(1)
1007 .ticker(ticker)
1008 .expireAfterAccess(1, TimeUnit.NANOSECONDS));
1009 Segment<Object, Object> segment = map.segments[0];
1010
1011
1012 Object key = new Object();
1013 int hash = map.hash(key);
1014 Object value = new Object();
1015 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1016 int index = hash & (table.length() - 1);
1017
1018 ReferenceEntry<Object, Object> entry = map.newEntry(key, hash, null);
1019 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value, 1);
1020 entry.setValueReference(valueRef);
1021
1022 assertNull(segment.get(key, hash));
1023
1024
1025 table.set(index, entry);
1026 assertNull(segment.get(key, hash));
1027 assertFalse(segment.containsKey(key, hash));
1028 assertFalse(segment.containsValue(value));
1029
1030
1031 segment.count++;
1032 assertSame(value, segment.get(key, hash));
1033 assertTrue(segment.containsKey(key, hash));
1034 assertTrue(segment.containsValue(value));
1035
1036 assertNull(segment.get(new Object(), hash));
1037
1038
1039 DummyEntry<Object, Object> nullEntry = DummyEntry.create(null, hash, entry);
1040 Object nullValue = new Object();
1041 ValueReference<Object, Object> nullValueRef = map.newValueReference(nullEntry, nullValue, 1);
1042 nullEntry.setValueReference(nullValueRef);
1043 table.set(index, nullEntry);
1044
1045 assertSame(value, segment.get(key, hash));
1046 assertTrue(segment.containsKey(key, hash));
1047 assertTrue(segment.containsValue(value));
1048 assertFalse(segment.containsValue(nullValue));
1049
1050
1051 DummyEntry<Object, Object> dummy = DummyEntry.create(new Object(), hash, entry);
1052 Object dummyValue = new Object();
1053 ValueReference<Object, Object> dummyValueRef = map.newValueReference(dummy, dummyValue, 1);
1054 dummy.setValueReference(dummyValueRef);
1055 table.set(index, dummy);
1056 assertSame(value, segment.get(key, hash));
1057 assertTrue(segment.containsKey(key, hash));
1058 assertTrue(segment.containsValue(value));
1059 assertTrue(segment.containsValue(dummyValue));
1060
1061
1062 dummy = DummyEntry.create(key, hash, entry);
1063 dummyValue = new Object();
1064 dummyValueRef = map.newValueReference(dummy, dummyValue, 1);
1065 dummy.setValueReference(dummyValueRef);
1066 table.set(index, dummy);
1067
1068 assertSame(dummyValue, segment.get(key, hash));
1069 assertTrue(segment.containsKey(key, hash));
1070 assertTrue(segment.containsValue(value));
1071 assertTrue(segment.containsValue(dummyValue));
1072
1073
1074 dummy.setAccessTime(ticker.read() - 2);
1075 assertNull(segment.get(key, hash));
1076 assertFalse(segment.containsKey(key, hash));
1077 assertTrue(segment.containsValue(value));
1078 assertFalse(segment.containsValue(dummyValue));
1079 }
1080
1081 public void testSegmentReplaceValue() {
1082 LocalCache<Object, Object> map =
1083 makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1084 Segment<Object, Object> segment = map.segments[0];
1085
1086
1087 Object key = new Object();
1088 int hash = map.hash(key);
1089 Object oldValue = new Object();
1090 Object newValue = new Object();
1091 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1092 int index = hash & (table.length() - 1);
1093
1094 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1095 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1096 entry.setValueReference(oldValueRef);
1097
1098
1099 assertFalse(segment.replace(key, hash, oldValue, newValue));
1100 assertEquals(0, segment.count);
1101
1102
1103 table.set(index, entry);
1104 segment.count++;
1105 assertEquals(1, segment.count);
1106 assertSame(oldValue, segment.get(key, hash));
1107 assertTrue(segment.replace(key, hash, oldValue, newValue));
1108 assertEquals(1, segment.count);
1109 assertSame(newValue, segment.get(key, hash));
1110
1111
1112 assertFalse(segment.replace(key, hash, oldValue, newValue));
1113 assertEquals(1, segment.count);
1114 assertSame(newValue, segment.get(key, hash));
1115
1116
1117 entry.setValueReference(oldValueRef);
1118 assertSame(oldValue, segment.get(key, hash));
1119 oldValueRef.clear();
1120 assertFalse(segment.replace(key, hash, oldValue, newValue));
1121 assertEquals(0, segment.count);
1122 assertNull(segment.get(key, hash));
1123 }
1124
1125 public void testSegmentReplace() {
1126 LocalCache<Object, Object> map =
1127 makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1128 Segment<Object, Object> segment = map.segments[0];
1129
1130
1131 Object key = new Object();
1132 int hash = map.hash(key);
1133 Object oldValue = new Object();
1134 Object newValue = new Object();
1135 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1136 int index = hash & (table.length() - 1);
1137
1138 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1139 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1140 entry.setValueReference(oldValueRef);
1141
1142
1143 assertNull(segment.replace(key, hash, newValue));
1144 assertEquals(0, segment.count);
1145
1146
1147 table.set(index, entry);
1148 segment.count++;
1149 assertEquals(1, segment.count);
1150 assertSame(oldValue, segment.get(key, hash));
1151 assertSame(oldValue, segment.replace(key, hash, newValue));
1152 assertEquals(1, segment.count);
1153 assertSame(newValue, segment.get(key, hash));
1154
1155
1156 entry.setValueReference(oldValueRef);
1157 assertSame(oldValue, segment.get(key, hash));
1158 oldValueRef.clear();
1159 assertNull(segment.replace(key, hash, newValue));
1160 assertEquals(0, segment.count);
1161 assertNull(segment.get(key, hash));
1162 }
1163
1164 public void testSegmentPut() {
1165 LocalCache<Object, Object> map =
1166 makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1167 Segment<Object, Object> segment = map.segments[0];
1168
1169
1170 Object key = new Object();
1171 int hash = map.hash(key);
1172 Object oldValue = new Object();
1173 Object newValue = new Object();
1174
1175
1176 assertEquals(0, segment.count);
1177 assertNull(segment.put(key, hash, oldValue, false));
1178 assertEquals(1, segment.count);
1179
1180
1181 assertSame(oldValue, segment.put(key, hash, newValue, false));
1182 assertEquals(1, segment.count);
1183 assertSame(newValue, segment.get(key, hash));
1184
1185
1186 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1187 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1188 entry.setValueReference(oldValueRef);
1189 assertSame(oldValue, segment.get(key, hash));
1190 oldValueRef.clear();
1191 assertNull(segment.put(key, hash, newValue, false));
1192 assertEquals(1, segment.count);
1193 assertSame(newValue, segment.get(key, hash));
1194 }
1195
1196 public void testSegmentPutIfAbsent() {
1197 LocalCache<Object, Object> map =
1198 makeLocalCache(createCacheBuilder().concurrencyLevel(1).expireAfterAccess(99999, SECONDS));
1199 Segment<Object, Object> segment = map.segments[0];
1200
1201
1202 Object key = new Object();
1203 int hash = map.hash(key);
1204 Object oldValue = new Object();
1205 Object newValue = new Object();
1206
1207
1208 assertEquals(0, segment.count);
1209 assertNull(segment.put(key, hash, oldValue, true));
1210 assertEquals(1, segment.count);
1211
1212
1213 assertSame(oldValue, segment.put(key, hash, newValue, true));
1214 assertEquals(1, segment.count);
1215 assertSame(oldValue, segment.get(key, hash));
1216
1217
1218 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1219 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1220 entry.setValueReference(oldValueRef);
1221 assertSame(oldValue, segment.get(key, hash));
1222 oldValueRef.clear();
1223 assertNull(segment.put(key, hash, newValue, true));
1224 assertEquals(1, segment.count);
1225 assertSame(newValue, segment.get(key, hash));
1226 }
1227
1228 public void testSegmentPut_expand() {
1229 LocalCache<Object, Object> map =
1230 makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1231 Segment<Object, Object> segment = map.segments[0];
1232 assertEquals(1, segment.table.length());
1233
1234 int count = 1024;
1235 for (int i = 0; i < count; i++) {
1236 Object key = new Object();
1237 Object value = new Object();
1238 int hash = map.hash(key);
1239 assertNull(segment.put(key, hash, value, false));
1240 assertTrue(segment.table.length() > i);
1241 }
1242 }
1243
1244 public void testSegmentPut_evict() {
1245 int maxSize = 10;
1246 LocalCache<Object, Object> map =
1247 makeLocalCache(createCacheBuilder().concurrencyLevel(1).maximumSize(maxSize));
1248
1249
1250 int originalCount = 1024;
1251 LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
1252 for (int i = 0; i < originalCount; i++) {
1253 Object key = new Object();
1254 Object value = new Object();
1255 map.put(key, value);
1256 originalMap.put(key, value);
1257 if (i >= maxSize) {
1258 Iterator<Object> it = originalMap.keySet().iterator();
1259 it.next();
1260 it.remove();
1261 }
1262 assertEquals(originalMap, map);
1263 }
1264 }
1265
1266 public void testSegmentStoreComputedValue() {
1267 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
1268 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1269 .concurrencyLevel(1)
1270 .removalListener(listener));
1271 Segment<Object, Object> segment = map.segments[0];
1272
1273 Object key = new Object();
1274 int hash = map.hash(key);
1275 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1276 int index = hash & (table.length() - 1);
1277
1278 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1279 LoadingValueReference<Object, Object> valueRef = new LoadingValueReference<Object, Object>();
1280 entry.setValueReference(valueRef);
1281
1282
1283 Object value = new Object();
1284 assertTrue(listener.isEmpty());
1285 assertEquals(0, segment.count);
1286 assertNull(segment.get(key, hash));
1287 assertTrue(segment.storeLoadedValue(key, hash, valueRef, value));
1288 assertSame(value, segment.get(key, hash));
1289 assertEquals(1, segment.count);
1290 assertTrue(listener.isEmpty());
1291
1292
1293 Object value2 = new Object();
1294 assertFalse(segment.storeLoadedValue(key, hash, valueRef, value2));
1295 assertEquals(1, segment.count);
1296 assertSame(value, segment.get(key, hash));
1297 RemovalNotification<Object, Object> notification = listener.remove();
1298 assertEquals(immutableEntry(key, value2), notification);
1299 assertEquals(RemovalCause.REPLACED, notification.getCause());
1300 assertTrue(listener.isEmpty());
1301
1302
1303 Object value3 = new Object();
1304 map.clear();
1305 listener.clear();
1306 assertEquals(0, segment.count);
1307 table.set(index, entry);
1308 assertTrue(segment.storeLoadedValue(key, hash, valueRef, value3));
1309 assertSame(value3, segment.get(key, hash));
1310 assertEquals(1, segment.count);
1311 assertTrue(listener.isEmpty());
1312
1313
1314 Object value4 = new Object();
1315 DummyValueReference<Object, Object> value3Ref = DummyValueReference.create(value3);
1316 valueRef = new LoadingValueReference<Object, Object>(value3Ref);
1317 entry.setValueReference(valueRef);
1318 table.set(index, entry);
1319 assertSame(value3, segment.get(key, hash));
1320 assertEquals(1, segment.count);
1321 assertTrue(segment.storeLoadedValue(key, hash, valueRef, value4));
1322 assertSame(value4, segment.get(key, hash));
1323 assertEquals(1, segment.count);
1324 notification = listener.remove();
1325 assertEquals(immutableEntry(key, value3), notification);
1326 assertEquals(RemovalCause.REPLACED, notification.getCause());
1327 assertTrue(listener.isEmpty());
1328
1329
1330 entry.setValueReference(valueRef);
1331 table.set(index, entry);
1332 assertSame(value3, segment.get(key, hash));
1333 assertEquals(1, segment.count);
1334 value3Ref.clear();
1335 assertTrue(segment.storeLoadedValue(key, hash, valueRef, value4));
1336 assertSame(value4, segment.get(key, hash));
1337 assertEquals(1, segment.count);
1338 notification = listener.remove();
1339 assertEquals(immutableEntry(key, null), notification);
1340 assertEquals(RemovalCause.COLLECTED, notification.getCause());
1341 assertTrue(listener.isEmpty());
1342 }
1343
1344 public void testSegmentRemove() {
1345 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().concurrencyLevel(1));
1346 Segment<Object, Object> segment = map.segments[0];
1347
1348 Object key = new Object();
1349 int hash = map.hash(key);
1350 Object oldValue = new Object();
1351 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1352 int index = hash & (table.length() - 1);
1353
1354 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1355 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1356 entry.setValueReference(oldValueRef);
1357
1358
1359 assertEquals(0, segment.count);
1360 assertNull(segment.remove(key, hash));
1361 assertEquals(0, segment.count);
1362
1363
1364 table.set(index, entry);
1365 segment.count++;
1366 assertEquals(1, segment.count);
1367 assertSame(oldValue, segment.get(key, hash));
1368 assertSame(oldValue, segment.remove(key, hash));
1369 assertEquals(0, segment.count);
1370 assertNull(segment.get(key, hash));
1371
1372
1373 table.set(index, entry);
1374 segment.count++;
1375 assertEquals(1, segment.count);
1376 assertSame(oldValue, segment.get(key, hash));
1377 oldValueRef.clear();
1378 assertNull(segment.remove(key, hash));
1379 assertEquals(0, segment.count);
1380 assertNull(segment.get(key, hash));
1381 }
1382
1383 public void testSegmentRemoveValue() {
1384 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().concurrencyLevel(1));
1385 Segment<Object, Object> segment = map.segments[0];
1386
1387 Object key = new Object();
1388 int hash = map.hash(key);
1389 Object oldValue = new Object();
1390 Object newValue = new Object();
1391 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1392 int index = hash & (table.length() - 1);
1393
1394 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1395 DummyValueReference<Object, Object> oldValueRef = DummyValueReference.create(oldValue);
1396 entry.setValueReference(oldValueRef);
1397
1398
1399 assertEquals(0, segment.count);
1400 assertNull(segment.remove(key, hash));
1401 assertEquals(0, segment.count);
1402
1403
1404 table.set(index, entry);
1405 segment.count++;
1406 assertEquals(1, segment.count);
1407 assertSame(oldValue, segment.get(key, hash));
1408 assertTrue(segment.remove(key, hash, oldValue));
1409 assertEquals(0, segment.count);
1410 assertNull(segment.get(key, hash));
1411
1412
1413 table.set(index, entry);
1414 segment.count++;
1415 assertEquals(1, segment.count);
1416 assertSame(oldValue, segment.get(key, hash));
1417 assertFalse(segment.remove(key, hash, newValue));
1418 assertEquals(1, segment.count);
1419 assertSame(oldValue, segment.get(key, hash));
1420
1421
1422 assertSame(oldValue, segment.get(key, hash));
1423 oldValueRef.clear();
1424 assertFalse(segment.remove(key, hash, oldValue));
1425 assertEquals(0, segment.count);
1426 assertNull(segment.get(key, hash));
1427 }
1428
1429 public void testExpand() {
1430 LocalCache<Object, Object> map =
1431 makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1432 Segment<Object, Object> segment = map.segments[0];
1433 assertEquals(1, segment.table.length());
1434
1435
1436 int originalCount = 1024;
1437 ReferenceEntry<Object, Object> entry = null;
1438 for (int i = 0; i < originalCount; i++) {
1439 Object key = new Object();
1440 Object value = new Object();
1441 int hash = map.hash(key);
1442
1443 entry = map.newEntry(key, hash, entry);
1444 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value, 1);
1445 entry.setValueReference(valueRef);
1446 }
1447 segment.table.set(0, entry);
1448 segment.count = originalCount;
1449 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
1450 assertEquals(originalCount, originalMap.size());
1451 assertEquals(originalMap, map);
1452
1453 for (int i = 1; i <= originalCount * 2; i *= 2) {
1454 if (i > 1) {
1455 segment.expand();
1456 }
1457 assertEquals(i, segment.table.length());
1458 assertEquals(originalCount, countLiveEntries(map, 0));
1459 assertEquals(originalCount, segment.count);
1460 assertEquals(originalMap, map);
1461 }
1462 }
1463
1464 public void testGetCausesExpansion() throws ExecutionException {
1465 for (int count = 1; count <= 100; count++) {
1466 LocalCache<Object, Object> map =
1467 makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1468 Segment<Object, Object> segment = map.segments[0];
1469 assertEquals(1, segment.table.length());
1470
1471 for (int i = 0; i < count; i++) {
1472 Object key = new Object();
1473 final Object value = new Object();
1474 segment.get(key, key.hashCode(), new CacheLoader<Object, Object>() {
1475 @Override
1476 public Object load(Object key) {
1477 return value;
1478 }
1479 });
1480 }
1481 assertEquals(count, segment.count);
1482 assertTrue(count <= segment.threshold);
1483 assertTrue(count <= (segment.table.length() * 3 / 4));
1484 assertTrue(count > (segment.table.length() * 3 / 8));
1485 }
1486 }
1487
1488 public void testPutCausesExpansion() {
1489 for (int count = 1; count <= 100; count++) {
1490 LocalCache<Object, Object> map =
1491 makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1492 Segment<Object, Object> segment = map.segments[0];
1493 assertEquals(1, segment.table.length());
1494
1495 for (int i = 0; i < count; i++) {
1496 Object key = new Object();
1497 Object value = new Object();
1498 segment.put(key, key.hashCode(), value, true);
1499 }
1500 assertEquals(count, segment.count);
1501 assertTrue(count <= segment.threshold);
1502 assertTrue(count <= (segment.table.length() * 3 / 4));
1503 assertTrue(count > (segment.table.length() * 3 / 8));
1504 }
1505 }
1506
1507 public void testReclaimKey() {
1508 CountingRemovalListener<Object, Object> listener = countingRemovalListener();
1509 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1510 .concurrencyLevel(1)
1511 .initialCapacity(1)
1512 .maximumSize(SMALL_MAX_SIZE)
1513 .expireAfterWrite(99999, SECONDS)
1514 .removalListener(listener));
1515 Segment<Object, Object> segment = map.segments[0];
1516 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1517 assertEquals(1, table.length());
1518
1519
1520 Object keyOne = new Object();
1521 Object valueOne = new Object();
1522 int hashOne = map.hash(keyOne);
1523 DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
1524 Object keyTwo = new Object();
1525 Object valueTwo = new Object();
1526 int hashTwo = map.hash(keyTwo);
1527 DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
1528 Object keyThree = new Object();
1529 Object valueThree = new Object();
1530 int hashThree = map.hash(keyThree);
1531 DummyEntry<Object, Object> entryThree =
1532 createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
1533
1534
1535 assertEquals(0, listener.getCount());
1536 assertFalse(segment.reclaimKey(entryOne, hashOne));
1537 assertEquals(0, listener.getCount());
1538 table.set(0, entryOne);
1539 assertFalse(segment.reclaimKey(entryTwo, hashTwo));
1540 assertEquals(0, listener.getCount());
1541 table.set(0, entryTwo);
1542 assertFalse(segment.reclaimKey(entryThree, hashThree));
1543 assertEquals(0, listener.getCount());
1544
1545
1546 table.set(0, entryOne);
1547 segment.count = 1;
1548 assertTrue(segment.reclaimKey(entryOne, hashOne));
1549 assertEquals(1, listener.getCount());
1550 assertSame(keyOne, listener.getLastEvictedKey());
1551 assertSame(valueOne, listener.getLastEvictedValue());
1552 assertTrue(map.removalNotificationQueue.isEmpty());
1553 assertFalse(segment.accessQueue.contains(entryOne));
1554 assertFalse(segment.writeQueue.contains(entryOne));
1555 assertEquals(0, segment.count);
1556 assertNull(table.get(0));
1557 }
1558
1559 public void testRemoveEntryFromChain() {
1560 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder().concurrencyLevel(1));
1561 Segment<Object, Object> segment = map.segments[0];
1562
1563
1564 Object keyOne = new Object();
1565 Object valueOne = new Object();
1566 int hashOne = map.hash(keyOne);
1567 DummyEntry<Object, Object> entryOne = createDummyEntry(keyOne, hashOne, valueOne, null);
1568 Object keyTwo = new Object();
1569 Object valueTwo = new Object();
1570 int hashTwo = map.hash(keyTwo);
1571 DummyEntry<Object, Object> entryTwo = createDummyEntry(keyTwo, hashTwo, valueTwo, entryOne);
1572 Object keyThree = new Object();
1573 Object valueThree = new Object();
1574 int hashThree = map.hash(keyThree);
1575 DummyEntry<Object, Object> entryThree =
1576 createDummyEntry(keyThree, hashThree, valueThree, entryTwo);
1577
1578
1579 assertNull(segment.removeEntryFromChain(entryOne, entryOne));
1580
1581
1582 assertSame(entryOne, segment.removeEntryFromChain(entryTwo, entryTwo));
1583
1584
1585 ReferenceEntry<Object, Object> newFirst = segment.removeEntryFromChain(entryThree, entryTwo);
1586 assertSame(keyThree, newFirst.getKey());
1587 assertSame(valueThree, newFirst.getValueReference().get());
1588 assertEquals(hashThree, newFirst.getHash());
1589 assertSame(entryOne, newFirst.getNext());
1590
1591
1592 newFirst = segment.removeEntryFromChain(entryThree, entryOne);
1593 assertSame(keyTwo, newFirst.getKey());
1594 assertSame(valueTwo, newFirst.getValueReference().get());
1595 assertEquals(hashTwo, newFirst.getHash());
1596 newFirst = newFirst.getNext();
1597 assertSame(keyThree, newFirst.getKey());
1598 assertSame(valueThree, newFirst.getValueReference().get());
1599 assertEquals(hashThree, newFirst.getHash());
1600 assertNull(newFirst.getNext());
1601 }
1602
1603 public void testExpand_cleanup() {
1604 LocalCache<Object, Object> map =
1605 makeLocalCache(createCacheBuilder().concurrencyLevel(1).initialCapacity(1));
1606 Segment<Object, Object> segment = map.segments[0];
1607 assertEquals(1, segment.table.length());
1608
1609
1610
1611 int originalCount = 1024;
1612 ReferenceEntry<Object, Object> entry = null;
1613 for (int i = 0; i < originalCount; i++) {
1614 Object key = new Object();
1615 Object value = (i % 3 == 0) ? null : new Object();
1616 int hash = map.hash(key);
1617 if (i % 3 == 1) {
1618 key = null;
1619 }
1620
1621 entry = DummyEntry.create(key, hash, entry);
1622 ValueReference<Object, Object> valueRef = DummyValueReference.create(value);
1623 entry.setValueReference(valueRef);
1624 }
1625 segment.table.set(0, entry);
1626 segment.count = originalCount;
1627 int liveCount = originalCount / 3;
1628 assertEquals(1, segment.table.length());
1629 assertEquals(liveCount, countLiveEntries(map, 0));
1630 ImmutableMap<Object, Object> originalMap = ImmutableMap.copyOf(map);
1631 assertEquals(liveCount, originalMap.size());
1632
1633
1634 for (int i = 1; i <= originalCount * 2; i *= 2) {
1635 if (i > 1) {
1636 segment.expand();
1637 }
1638 assertEquals(i, segment.table.length());
1639 assertEquals(liveCount, countLiveEntries(map, 0));
1640
1641 assertTrue(segment.count >= liveCount);
1642 assertTrue(segment.count <= originalCount);
1643 assertEquals(originalMap, ImmutableMap.copyOf(map));
1644 }
1645 }
1646
1647 private static <K, V> int countLiveEntries(LocalCache<K, V> map, long now) {
1648 int result = 0;
1649 for (Segment<K, V> segment : map.segments) {
1650 AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
1651 for (int i = 0; i < table.length(); i++) {
1652 for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
1653 if (map.isLive(e, now)) {
1654 result++;
1655 }
1656 }
1657 }
1658 }
1659 return result;
1660 }
1661
1662 public void testClear() {
1663 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1664 .concurrencyLevel(1)
1665 .initialCapacity(1)
1666 .maximumSize(SMALL_MAX_SIZE)
1667 .expireAfterWrite(99999, SECONDS));
1668 Segment<Object, Object> segment = map.segments[0];
1669 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1670 assertEquals(1, table.length());
1671
1672 Object key = new Object();
1673 Object value = new Object();
1674 int hash = map.hash(key);
1675 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1676 segment.recordWrite(entry, 1, map.ticker.read());
1677 segment.table.set(0, entry);
1678 segment.readCount.incrementAndGet();
1679 segment.count = 1;
1680 segment.totalWeight = 1;
1681
1682 assertSame(entry, table.get(0));
1683 assertSame(entry, segment.accessQueue.peek());
1684 assertSame(entry, segment.writeQueue.peek());
1685
1686 segment.clear();
1687 assertNull(table.get(0));
1688 assertTrue(segment.accessQueue.isEmpty());
1689 assertTrue(segment.writeQueue.isEmpty());
1690 assertEquals(0, segment.readCount.get());
1691 assertEquals(0, segment.count);
1692 assertEquals(0, segment.totalWeight);
1693 }
1694
1695 public void testClear_notification() {
1696 QueuingRemovalListener<Object, Object> listener = queuingRemovalListener();
1697 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1698 .concurrencyLevel(1)
1699 .initialCapacity(1)
1700 .maximumSize(SMALL_MAX_SIZE)
1701 .expireAfterWrite(99999, SECONDS)
1702 .removalListener(listener));
1703 Segment<Object, Object> segment = map.segments[0];
1704 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1705 assertEquals(1, table.length());
1706
1707 Object key = new Object();
1708 Object value = new Object();
1709 int hash = map.hash(key);
1710 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1711 segment.recordWrite(entry, 1, map.ticker.read());
1712 segment.table.set(0, entry);
1713 segment.readCount.incrementAndGet();
1714 segment.count = 1;
1715 segment.totalWeight = 1;
1716
1717 assertSame(entry, table.get(0));
1718 assertSame(entry, segment.accessQueue.peek());
1719 assertSame(entry, segment.writeQueue.peek());
1720
1721 segment.clear();
1722 assertNull(table.get(0));
1723 assertTrue(segment.accessQueue.isEmpty());
1724 assertTrue(segment.writeQueue.isEmpty());
1725 assertEquals(0, segment.readCount.get());
1726 assertEquals(0, segment.count);
1727 assertEquals(0, segment.totalWeight);
1728 assertNotified(listener, key, value, RemovalCause.EXPLICIT);
1729 }
1730
1731 public void testRemoveEntry() {
1732 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1733 .concurrencyLevel(1)
1734 .initialCapacity(1)
1735 .maximumSize(SMALL_MAX_SIZE)
1736 .expireAfterWrite(99999, SECONDS)
1737 .removalListener(countingRemovalListener()));
1738 Segment<Object, Object> segment = map.segments[0];
1739 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1740 assertEquals(1, table.length());
1741
1742 Object key = new Object();
1743 Object value = new Object();
1744 int hash = map.hash(key);
1745 DummyEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1746
1747
1748 assertFalse(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1749
1750
1751 segment.recordWrite(entry, 1, map.ticker.read());
1752 table.set(0, entry);
1753 segment.count = 1;
1754 assertTrue(segment.removeEntry(entry, hash, RemovalCause.COLLECTED));
1755 assertNotificationEnqueued(map, key, value, hash);
1756 assertTrue(map.removalNotificationQueue.isEmpty());
1757 assertFalse(segment.accessQueue.contains(entry));
1758 assertFalse(segment.writeQueue.contains(entry));
1759 assertEquals(0, segment.count);
1760 assertNull(table.get(0));
1761 }
1762
1763 public void testReclaimValue() {
1764 CountingRemovalListener<Object, Object> listener =
1765 countingRemovalListener();
1766 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1767 .concurrencyLevel(1)
1768 .initialCapacity(1)
1769 .maximumSize(SMALL_MAX_SIZE)
1770 .expireAfterWrite(99999, SECONDS)
1771 .removalListener(listener));
1772 Segment<Object, Object> segment = map.segments[0];
1773 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1774 assertEquals(1, table.length());
1775
1776 Object key = new Object();
1777 Object value = new Object();
1778 int hash = map.hash(key);
1779 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1780 DummyValueReference<Object, Object> valueRef = DummyValueReference.create(value);
1781 entry.setValueReference(valueRef);
1782
1783
1784 assertFalse(segment.reclaimValue(key, hash, valueRef));
1785
1786
1787 segment.recordWrite(entry, 1, map.ticker.read());
1788 table.set(0, entry);
1789 segment.count = 1;
1790 assertTrue(segment.reclaimValue(key, hash, valueRef));
1791 assertEquals(1, listener.getCount());
1792 assertSame(key, listener.getLastEvictedKey());
1793 assertSame(value, listener.getLastEvictedValue());
1794 assertTrue(map.removalNotificationQueue.isEmpty());
1795 assertFalse(segment.accessQueue.contains(entry));
1796 assertFalse(segment.writeQueue.contains(entry));
1797 assertEquals(0, segment.count);
1798 assertNull(table.get(0));
1799
1800
1801 table.set(0, entry);
1802 DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value);
1803 entry.setValueReference(otherValueRef);
1804 assertFalse(segment.reclaimValue(key, hash, valueRef));
1805 assertEquals(1, listener.getCount());
1806 assertTrue(segment.reclaimValue(key, hash, otherValueRef));
1807 assertEquals(2, listener.getCount());
1808 assertSame(key, listener.getLastEvictedKey());
1809 assertSame(value, listener.getLastEvictedValue());
1810 }
1811
1812 public void testRemoveComputingValue() {
1813 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
1814 .concurrencyLevel(1)
1815 .initialCapacity(1)
1816 .maximumSize(SMALL_MAX_SIZE)
1817 .expireAfterWrite(99999, SECONDS)
1818 .removalListener(countingRemovalListener()));
1819 Segment<Object, Object> segment = map.segments[0];
1820 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
1821 assertEquals(1, table.length());
1822
1823 Object key = new Object();
1824 int hash = map.hash(key);
1825 DummyEntry<Object, Object> entry = DummyEntry.create(key, hash, null);
1826 LoadingValueReference<Object, Object> valueRef = new LoadingValueReference<Object, Object>();
1827 entry.setValueReference(valueRef);
1828
1829
1830 assertFalse(segment.removeLoadingValue(key, hash, valueRef));
1831
1832
1833 table.set(0, entry);
1834
1835 assertTrue(segment.removeLoadingValue(key, hash, valueRef));
1836
1837 assertTrue(map.removalNotificationQueue.isEmpty());
1838 assertEquals(0, segment.count);
1839 assertNull(table.get(0));
1840
1841
1842 Object value = new Object();
1843 DummyValueReference<Object, Object> previousRef = DummyValueReference.create(value);
1844 valueRef = new LoadingValueReference<Object, Object>(previousRef);
1845 entry.setValueReference(valueRef);
1846 table.set(0, entry);
1847 segment.count = 1;
1848 assertTrue(segment.removeLoadingValue(key, hash, valueRef));
1849 assertSame(entry, table.get(0));
1850 assertSame(value, segment.get(key, hash));
1851
1852
1853 table.set(0, entry);
1854 DummyValueReference<Object, Object> otherValueRef = DummyValueReference.create(value);
1855 entry.setValueReference(otherValueRef);
1856 assertFalse(segment.removeLoadingValue(key, hash, valueRef));
1857 entry.setValueReference(valueRef);
1858 assertTrue(segment.removeLoadingValue(key, hash, valueRef));
1859 }
1860
1861 private static <K, V> void assertNotificationEnqueued(
1862 LocalCache<K, V> map, K key, V value, int hash) {
1863 RemovalNotification<K, V> notification = map.removalNotificationQueue.poll();
1864 assertSame(key, notification.getKey());
1865 assertSame(value, notification.getValue());
1866 }
1867
1868
1869
1870 public void testDrainRecencyQueueOnWrite() {
1871 for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1872 LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1873 Segment<Object, Object> segment = map.segments[0];
1874
1875 if (segment.recencyQueue != DISCARDING_QUEUE) {
1876 Object keyOne = new Object();
1877 Object valueOne = new Object();
1878 Object keyTwo = new Object();
1879 Object valueTwo = new Object();
1880
1881 map.put(keyOne, valueOne);
1882 assertTrue(segment.recencyQueue.isEmpty());
1883
1884 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1885 map.get(keyOne);
1886 }
1887 assertFalse(segment.recencyQueue.isEmpty());
1888
1889 map.put(keyTwo, valueTwo);
1890 assertTrue(segment.recencyQueue.isEmpty());
1891 }
1892 }
1893 }
1894
1895 public void testDrainRecencyQueueOnRead() {
1896 for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1897 LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1898 Segment<Object, Object> segment = map.segments[0];
1899
1900 if (segment.recencyQueue != DISCARDING_QUEUE) {
1901 Object keyOne = new Object();
1902 Object valueOne = new Object();
1903
1904
1905
1906 map.put(keyOne, valueOne);
1907 assertTrue(segment.recencyQueue.isEmpty());
1908
1909 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1910 map.get(keyOne);
1911 }
1912 assertFalse(segment.recencyQueue.isEmpty());
1913
1914 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1915 map.get(keyOne);
1916 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1917 }
1918
1919
1920
1921 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1922 map.put(new Object(), new Object());
1923 }
1924 assertTrue(segment.recencyQueue.isEmpty());
1925
1926 for (int i = 0; i < DRAIN_THRESHOLD / 2; i++) {
1927 map.get(keyOne);
1928 }
1929 assertFalse(segment.recencyQueue.isEmpty());
1930
1931 for (Object key : map.keySet()) {
1932 map.get(key);
1933 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
1934 }
1935 }
1936 }
1937 }
1938
1939 public void testRecordRead() {
1940 for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1941 LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1942 Segment<Object, Object> segment = map.segments[0];
1943 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1944 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1945 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1946 Object key = new Object();
1947 int hash = map.hash(key);
1948 Object value = new Object();
1949
1950 ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
1951
1952 segment.recordWrite(entry, 1, map.ticker.read());
1953 writeOrder.add(entry);
1954 readOrder.add(entry);
1955 }
1956
1957 checkEvictionQueues(map, segment, readOrder, writeOrder);
1958 checkExpirationTimes(map);
1959
1960
1961 Random random = new Random();
1962 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
1963 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
1964 while (i.hasNext()) {
1965 ReferenceEntry<Object, Object> entry = i.next();
1966 if (random.nextBoolean()) {
1967 segment.recordRead(entry, map.ticker.read());
1968 reads.add(entry);
1969 i.remove();
1970 }
1971 }
1972 checkAndDrainRecencyQueue(map, segment, reads);
1973 readOrder.addAll(reads);
1974
1975 checkEvictionQueues(map, segment, readOrder, writeOrder);
1976 checkExpirationTimes(map);
1977 }
1978 }
1979
1980 public void testRecordReadOnGet() {
1981 for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
1982 LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
1983 Segment<Object, Object> segment = map.segments[0];
1984 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
1985 List<ReferenceEntry<Object, Object>> readOrder = Lists.newLinkedList();
1986 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
1987 Object key = new Object();
1988 int hash = map.hash(key);
1989 Object value = new Object();
1990
1991 map.put(key, value);
1992 ReferenceEntry<Object, Object> entry = segment.getEntry(key, hash);
1993 writeOrder.add(entry);
1994 readOrder.add(entry);
1995 }
1996
1997 checkEvictionQueues(map, segment, readOrder, writeOrder);
1998 checkExpirationTimes(map);
1999 assertTrue(segment.recencyQueue.isEmpty());
2000
2001
2002 Random random = new Random();
2003 List<ReferenceEntry<Object, Object>> reads = Lists.newArrayList();
2004 Iterator<ReferenceEntry<Object, Object>> i = readOrder.iterator();
2005 while (i.hasNext()) {
2006 ReferenceEntry<Object, Object> entry = i.next();
2007 if (random.nextBoolean()) {
2008 map.get(entry.getKey());
2009 reads.add(entry);
2010 i.remove();
2011 assertTrue(segment.recencyQueue.size() <= DRAIN_THRESHOLD);
2012 }
2013 }
2014 int undrainedIndex = reads.size() - segment.recencyQueue.size();
2015 checkAndDrainRecencyQueue(map, segment, reads.subList(undrainedIndex, reads.size()));
2016 readOrder.addAll(reads);
2017
2018 checkEvictionQueues(map, segment, readOrder, writeOrder);
2019 checkExpirationTimes(map);
2020 }
2021 }
2022
2023 public void testRecordWrite() {
2024 for (CacheBuilder<Object, Object> builder : allEvictingMakers()) {
2025 LocalCache<Object, Object> map = makeLocalCache(builder.concurrencyLevel(1));
2026 Segment<Object, Object> segment = map.segments[0];
2027 List<ReferenceEntry<Object, Object>> writeOrder = Lists.newLinkedList();
2028 for (int i = 0; i < DRAIN_THRESHOLD * 2; i++) {
2029 Object key = new Object();
2030 int hash = map.hash(key);
2031 Object value = new Object();
2032
2033 ReferenceEntry<Object, Object> entry = createDummyEntry(key, hash, value, null);
2034
2035 segment.recordWrite(entry, 1, map.ticker.read());
2036 writeOrder.add(entry);
2037 }
2038
2039 checkEvictionQueues(map, segment, writeOrder, writeOrder);
2040 checkExpirationTimes(map);
2041
2042
2043 Random random = new Random();
2044 List<ReferenceEntry<Object, Object>> writes = Lists.newArrayList();
2045 Iterator<ReferenceEntry<Object, Object>> i = writeOrder.iterator();
2046 while (i.hasNext()) {
2047 ReferenceEntry<Object, Object> entry = i.next();
2048 if (random.nextBoolean()) {
2049 segment.recordWrite(entry, 1, map.ticker.read());
2050 writes.add(entry);
2051 i.remove();
2052 }
2053 }
2054 writeOrder.addAll(writes);
2055
2056 checkEvictionQueues(map, segment, writeOrder, writeOrder);
2057 checkExpirationTimes(map);
2058 }
2059 }
2060
2061 static <K, V> void checkAndDrainRecencyQueue(LocalCache<K, V> map,
2062 Segment<K, V> segment, List<ReferenceEntry<K, V>> reads) {
2063 if (map.evictsBySize() || map.expiresAfterAccess()) {
2064 assertSameEntries(reads, ImmutableList.copyOf(segment.recencyQueue));
2065 }
2066 segment.drainRecencyQueue();
2067 }
2068
2069 static <K, V> void checkEvictionQueues(LocalCache<K, V> map,
2070 Segment<K, V> segment, List<ReferenceEntry<K, V>> readOrder,
2071 List<ReferenceEntry<K, V>> writeOrder) {
2072 if (map.evictsBySize() || map.expiresAfterAccess()) {
2073 assertSameEntries(readOrder, ImmutableList.copyOf(segment.accessQueue));
2074 }
2075 if (map.expiresAfterWrite()) {
2076 assertSameEntries(writeOrder, ImmutableList.copyOf(segment.writeQueue));
2077 }
2078 }
2079
2080 private static <K, V> void assertSameEntries(List<ReferenceEntry<K, V>> expectedEntries,
2081 List<ReferenceEntry<K, V>> actualEntries) {
2082 int size = expectedEntries.size();
2083 assertEquals(size, actualEntries.size());
2084 for (int i = 0; i < size; i++) {
2085 ReferenceEntry<K, V> expectedEntry = expectedEntries.get(i);
2086 ReferenceEntry<K, V> actualEntry = actualEntries.get(i);
2087 assertSame(expectedEntry.getKey(), actualEntry.getKey());
2088 assertSame(expectedEntry.getValueReference().get(), actualEntry.getValueReference().get());
2089 }
2090 }
2091
2092 static <K, V> void checkExpirationTimes(LocalCache<K, V> map) {
2093 if (!map.expires()) {
2094 return;
2095 }
2096
2097 for (Segment<K, V> segment : map.segments) {
2098 long lastAccessTime = 0;
2099 long lastWriteTime = 0;
2100 for (ReferenceEntry<K, V> e : segment.recencyQueue) {
2101 long accessTime = e.getAccessTime();
2102 assertTrue(accessTime >= lastAccessTime);
2103 lastAccessTime = accessTime;
2104 long writeTime = e.getWriteTime();
2105 assertTrue(writeTime >= lastWriteTime);
2106 lastWriteTime = writeTime;
2107 }
2108
2109 lastAccessTime = 0;
2110 lastWriteTime = 0;
2111 for (ReferenceEntry<K, V> e : segment.accessQueue) {
2112 long accessTime = e.getAccessTime();
2113 assertTrue(accessTime >= lastAccessTime);
2114 lastAccessTime = accessTime;
2115 }
2116 for (ReferenceEntry<K, V> e : segment.writeQueue) {
2117 long writeTime = e.getWriteTime();
2118 assertTrue(writeTime >= lastWriteTime);
2119 lastWriteTime = writeTime;
2120 }
2121 }
2122 }
2123
2124 public void testExpireAfterWrite() {
2125 FakeTicker ticker = new FakeTicker();
2126 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
2127 .concurrencyLevel(1)
2128 .ticker(ticker)
2129 .expireAfterWrite(2, TimeUnit.NANOSECONDS));
2130 Segment<Object, Object> segment = map.segments[0];
2131
2132 Object key = new Object();
2133 Object value = new Object();
2134 map.put(key, value);
2135 ReferenceEntry<Object, Object> entry = map.getEntry(key);
2136 assertTrue(map.isLive(entry, ticker.read()));
2137
2138 segment.writeQueue.add(entry);
2139 assertSame(value, map.get(key));
2140 assertSame(entry, segment.writeQueue.peek());
2141 assertEquals(1, segment.writeQueue.size());
2142
2143 segment.recordRead(entry, ticker.read());
2144 segment.expireEntries(ticker.read());
2145 assertSame(value, map.get(key));
2146 assertSame(entry, segment.writeQueue.peek());
2147 assertEquals(1, segment.writeQueue.size());
2148
2149 ticker.advance(1);
2150 segment.recordRead(entry, ticker.read());
2151 segment.expireEntries(ticker.read());
2152 assertSame(value, map.get(key));
2153 assertSame(entry, segment.writeQueue.peek());
2154 assertEquals(1, segment.writeQueue.size());
2155
2156 ticker.advance(1);
2157 assertNull(map.get(key));
2158 segment.expireEntries(ticker.read());
2159 assertNull(map.get(key));
2160 assertTrue(segment.writeQueue.isEmpty());
2161 }
2162
2163 public void testExpireAfterAccess() {
2164 FakeTicker ticker = new FakeTicker();
2165 LocalCache<Object, Object> map = makeLocalCache(createCacheBuilder()
2166 .concurrencyLevel(1)
2167 .ticker(ticker)
2168 .expireAfterAccess(2, TimeUnit.NANOSECONDS));
2169 Segment<Object, Object> segment = map.segments[0];
2170
2171 Object key = new Object();
2172 Object value = new Object();
2173 map.put(key, value);
2174 ReferenceEntry<Object, Object> entry = map.getEntry(key);
2175 assertTrue(map.isLive(entry, ticker.read()));
2176
2177 segment.accessQueue.add(entry);
2178 assertSame(value, map.get(key));
2179 assertSame(entry, segment.accessQueue.peek());
2180 assertEquals(1, segment.accessQueue.size());
2181
2182 segment.recordRead(entry, ticker.read());
2183 segment.expireEntries(ticker.read());
2184 assertTrue(map.containsKey(key));
2185 assertSame(entry, segment.accessQueue.peek());
2186 assertEquals(1, segment.accessQueue.size());
2187
2188 ticker.advance(1);
2189 segment.recordRead(entry, ticker.read());
2190 segment.expireEntries(ticker.read());
2191 assertTrue(map.containsKey(key));
2192 assertSame(entry, segment.accessQueue.peek());
2193 assertEquals(1, segment.accessQueue.size());
2194
2195 ticker.advance(1);
2196 segment.recordRead(entry, ticker.read());
2197 segment.expireEntries(ticker.read());
2198 assertTrue(map.containsKey(key));
2199 assertSame(entry, segment.accessQueue.peek());
2200 assertEquals(1, segment.accessQueue.size());
2201
2202 ticker.advance(1);
2203 segment.expireEntries(ticker.read());
2204 assertTrue(map.containsKey(key));
2205 assertSame(entry, segment.accessQueue.peek());
2206 assertEquals(1, segment.accessQueue.size());
2207
2208 ticker.advance(1);
2209 assertFalse(map.containsKey(key));
2210 assertNull(map.get(key));
2211 segment.expireEntries(ticker.read());
2212 assertFalse(map.containsKey(key));
2213 assertNull(map.get(key));
2214 assertTrue(segment.accessQueue.isEmpty());
2215 }
2216
2217 public void testEvictEntries() {
2218 int maxSize = 10;
2219 LocalCache<Object, Object> map =
2220 makeLocalCache(createCacheBuilder().concurrencyLevel(1).maximumSize(maxSize));
2221 Segment<Object, Object> segment = map.segments[0];
2222
2223
2224 int originalCount = 1024;
2225 ReferenceEntry<Object, Object> entry = null;
2226 LinkedHashMap<Object, Object> originalMap = Maps.newLinkedHashMap();
2227 for (int i = 0; i < originalCount; i++) {
2228 Object key = new Object();
2229 Object value = new Object();
2230 AtomicReferenceArray<ReferenceEntry<Object, Object>> table = segment.table;
2231 int hash = map.hash(key);
2232 int index = hash & (table.length() - 1);
2233 ReferenceEntry<Object, Object> first = table.get(index);
2234 entry = map.newEntry(key, hash, first);
2235 ValueReference<Object, Object> valueRef = map.newValueReference(entry, value, 1);
2236 entry.setValueReference(valueRef);
2237 segment.recordWrite(entry, 1, map.ticker.read());
2238 table.set(index, entry);
2239 originalMap.put(key, value);
2240 }
2241 segment.count = originalCount;
2242 segment.totalWeight = originalCount;
2243 assertEquals(originalCount, map.size());
2244 assertEquals(originalMap, map);
2245
2246 Iterator<Object> it = originalMap.keySet().iterator();
2247 for (int i = 0; i < originalCount - maxSize; i++) {
2248 it.next();
2249 it.remove();
2250 }
2251 segment.evictEntries();
2252 assertEquals(maxSize, map.size());
2253 assertEquals(originalMap, map);
2254 }
2255
2256
2257
2258 public void testDrainKeyReferenceQueueOnWrite() {
2259 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2260 LocalCache<Object, Object> map =
2261 makeLocalCache(builder.concurrencyLevel(1));
2262 if (map.usesKeyReferences()) {
2263 Segment<Object, Object> segment = map.segments[0];
2264
2265 Object keyOne = new Object();
2266 int hashOne = map.hash(keyOne);
2267 Object valueOne = new Object();
2268 Object keyTwo = new Object();
2269 Object valueTwo = new Object();
2270
2271 map.put(keyOne, valueOne);
2272 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2273
2274 @SuppressWarnings("unchecked")
2275 Reference<Object> reference = (Reference) entry;
2276 reference.enqueue();
2277
2278 map.put(keyTwo, valueTwo);
2279 assertFalse(map.containsKey(keyOne));
2280 assertFalse(map.containsValue(valueOne));
2281 assertNull(map.get(keyOne));
2282 assertEquals(1, map.size());
2283 assertNull(segment.keyReferenceQueue.poll());
2284 }
2285 }
2286 }
2287
2288 public void testDrainValueReferenceQueueOnWrite() {
2289 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2290 LocalCache<Object, Object> map =
2291 makeLocalCache(builder.concurrencyLevel(1));
2292 if (map.usesValueReferences()) {
2293 Segment<Object, Object> segment = map.segments[0];
2294
2295 Object keyOne = new Object();
2296 int hashOne = map.hash(keyOne);
2297 Object valueOne = new Object();
2298 Object keyTwo = new Object();
2299 Object valueTwo = new Object();
2300
2301 map.put(keyOne, valueOne);
2302 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2303 ValueReference<Object, Object> valueReference = entry.getValueReference();
2304
2305 @SuppressWarnings("unchecked")
2306 Reference<Object> reference = (Reference) valueReference;
2307 reference.enqueue();
2308
2309 map.put(keyTwo, valueTwo);
2310 assertFalse(map.containsKey(keyOne));
2311 assertFalse(map.containsValue(valueOne));
2312 assertNull(map.get(keyOne));
2313 assertEquals(1, map.size());
2314 assertNull(segment.valueReferenceQueue.poll());
2315 }
2316 }
2317 }
2318
2319 public void testDrainKeyReferenceQueueOnRead() {
2320 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2321 LocalCache<Object, Object> map =
2322 makeLocalCache(builder.concurrencyLevel(1));
2323 if (map.usesKeyReferences()) {
2324 Segment<Object, Object> segment = map.segments[0];
2325
2326 Object keyOne = new Object();
2327 int hashOne = map.hash(keyOne);
2328 Object valueOne = new Object();
2329 Object keyTwo = new Object();
2330
2331 map.put(keyOne, valueOne);
2332 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2333
2334 @SuppressWarnings("unchecked")
2335 Reference<Object> reference = (Reference) entry;
2336 reference.enqueue();
2337
2338 for (int i = 0; i < SMALL_MAX_SIZE; i++) {
2339 map.get(keyTwo);
2340 }
2341 assertFalse(map.containsKey(keyOne));
2342 assertFalse(map.containsValue(valueOne));
2343 assertNull(map.get(keyOne));
2344 assertEquals(0, map.size());
2345 assertNull(segment.keyReferenceQueue.poll());
2346 }
2347 }
2348 }
2349
2350 public void testDrainValueReferenceQueueOnRead() {
2351 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2352 LocalCache<Object, Object> map =
2353 makeLocalCache(builder.concurrencyLevel(1));
2354 if (map.usesValueReferences()) {
2355 Segment<Object, Object> segment = map.segments[0];
2356
2357 Object keyOne = new Object();
2358 int hashOne = map.hash(keyOne);
2359 Object valueOne = new Object();
2360 Object keyTwo = new Object();
2361
2362 map.put(keyOne, valueOne);
2363 ReferenceEntry<Object, Object> entry = segment.getEntry(keyOne, hashOne);
2364 ValueReference<Object, Object> valueReference = entry.getValueReference();
2365
2366 @SuppressWarnings("unchecked")
2367 Reference<Object> reference = (Reference) valueReference;
2368 reference.enqueue();
2369
2370 for (int i = 0; i < SMALL_MAX_SIZE; i++) {
2371 map.get(keyTwo);
2372 }
2373 assertFalse(map.containsKey(keyOne));
2374 assertFalse(map.containsValue(valueOne));
2375 assertNull(map.get(keyOne));
2376 assertEquals(0, map.size());
2377 assertNull(segment.valueReferenceQueue.poll());
2378 }
2379 }
2380 }
2381
2382 public void testNullParameters() throws Exception {
2383 NullPointerTester tester = new NullPointerTester();
2384 tester.testAllPublicInstanceMethods(makeLocalCache(createCacheBuilder()));
2385 CacheLoader<Object, Object> loader = identityLoader();
2386 tester.testAllPublicInstanceMethods(makeLocalCache(createCacheBuilder()));
2387 }
2388
2389 public void testSerializationProxyLoading() {
2390 CacheLoader<Object, Object> loader = new SerializableCacheLoader();
2391 RemovalListener<Object, Object> listener = new SerializableRemovalListener<Object, Object>();
2392 SerializableWeigher<Object, Object> weigher = new SerializableWeigher<Object, Object>();
2393 Ticker ticker = new SerializableTicker();
2394 @SuppressWarnings("unchecked")
2395 LocalLoadingCache<Object, Object> one = (LocalLoadingCache) CacheBuilder.newBuilder()
2396 .weakKeys()
2397 .softValues()
2398 .expireAfterAccess(123, SECONDS)
2399 .expireAfterWrite(456, MINUTES)
2400 .maximumWeight(789)
2401 .weigher(weigher)
2402 .concurrencyLevel(12)
2403 .removalListener(listener)
2404 .ticker(ticker)
2405 .build(loader);
2406
2407 one.getUnchecked(new Object());
2408 assertEquals(1, one.size());
2409 assertFalse(one.asMap().isEmpty());
2410 LocalLoadingCache<Object, Object> two = SerializableTester.reserialize(one);
2411 assertEquals(0, two.size());
2412 assertTrue(two.asMap().isEmpty());
2413
2414 LocalCache<Object, Object> localCacheOne = one.localCache;
2415 LocalCache<Object, Object> localCacheTwo = two.localCache;
2416
2417 assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2418 assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2419 assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2420 assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2421 assertEquals(localCacheOne.maxWeight, localCacheTwo.maxWeight);
2422 assertEquals(localCacheOne.weigher, localCacheTwo.weigher);
2423 assertEquals(localCacheOne.expireAfterAccessNanos, localCacheTwo.expireAfterAccessNanos);
2424 assertEquals(localCacheOne.expireAfterWriteNanos, localCacheTwo.expireAfterWriteNanos);
2425 assertEquals(localCacheOne.refreshNanos, localCacheTwo.refreshNanos);
2426 assertEquals(localCacheOne.removalListener, localCacheTwo.removalListener);
2427 assertEquals(localCacheOne.ticker, localCacheTwo.ticker);
2428
2429
2430 LocalLoadingCache<Object, Object> three = SerializableTester.reserialize(two);
2431 LocalCache<Object, Object> localCacheThree = three.localCache;
2432
2433 assertEquals(localCacheTwo.defaultLoader, localCacheThree.defaultLoader);
2434 assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2435 assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2436 assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2437 assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2438 assertEquals(localCacheTwo.maxWeight, localCacheThree.maxWeight);
2439 assertEquals(localCacheTwo.weigher, localCacheThree.weigher);
2440 assertEquals(localCacheTwo.expireAfterAccessNanos, localCacheThree.expireAfterAccessNanos);
2441 assertEquals(localCacheTwo.expireAfterWriteNanos, localCacheThree.expireAfterWriteNanos);
2442 assertEquals(localCacheTwo.removalListener, localCacheThree.removalListener);
2443 assertEquals(localCacheTwo.ticker, localCacheThree.ticker);
2444 }
2445
2446 public void testSerializationProxyManual() {
2447 RemovalListener<Object, Object> listener = new SerializableRemovalListener<Object, Object>();
2448 SerializableWeigher<Object, Object> weigher = new SerializableWeigher<Object, Object>();
2449 Ticker ticker = new SerializableTicker();
2450 @SuppressWarnings("unchecked")
2451 LocalManualCache<Object, Object> one = (LocalManualCache) CacheBuilder.newBuilder()
2452 .weakKeys()
2453 .softValues()
2454 .expireAfterAccess(123, NANOSECONDS)
2455 .maximumWeight(789)
2456 .weigher(weigher)
2457 .concurrencyLevel(12)
2458 .removalListener(listener)
2459 .ticker(ticker)
2460 .build();
2461
2462 one.put(new Object(), new Object());
2463 assertEquals(1, one.size());
2464 assertFalse(one.asMap().isEmpty());
2465 LocalManualCache<Object, Object> two = SerializableTester.reserialize(one);
2466 assertEquals(0, two.size());
2467 assertTrue(two.asMap().isEmpty());
2468
2469 LocalCache<Object, Object> localCacheOne = one.localCache;
2470 LocalCache<Object, Object> localCacheTwo = two.localCache;
2471
2472 assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2473 assertEquals(localCacheOne.keyStrength, localCacheTwo.keyStrength);
2474 assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2475 assertEquals(localCacheOne.valueEquivalence, localCacheTwo.valueEquivalence);
2476 assertEquals(localCacheOne.maxWeight, localCacheTwo.maxWeight);
2477 assertEquals(localCacheOne.weigher, localCacheTwo.weigher);
2478 assertEquals(localCacheOne.expireAfterAccessNanos, localCacheTwo.expireAfterAccessNanos);
2479 assertEquals(localCacheOne.expireAfterWriteNanos, localCacheTwo.expireAfterWriteNanos);
2480 assertEquals(localCacheOne.removalListener, localCacheTwo.removalListener);
2481 assertEquals(localCacheOne.ticker, localCacheTwo.ticker);
2482
2483
2484 LocalManualCache<Object, Object> three = SerializableTester.reserialize(two);
2485 LocalCache<Object, Object> localCacheThree = three.localCache;
2486
2487 assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2488 assertEquals(localCacheTwo.keyStrength, localCacheThree.keyStrength);
2489 assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2490 assertEquals(localCacheTwo.valueEquivalence, localCacheThree.valueEquivalence);
2491 assertEquals(localCacheTwo.maxWeight, localCacheThree.maxWeight);
2492 assertEquals(localCacheTwo.weigher, localCacheThree.weigher);
2493 assertEquals(localCacheTwo.expireAfterAccessNanos, localCacheThree.expireAfterAccessNanos);
2494 assertEquals(localCacheTwo.expireAfterWriteNanos, localCacheThree.expireAfterWriteNanos);
2495 assertEquals(localCacheTwo.removalListener, localCacheThree.removalListener);
2496 assertEquals(localCacheTwo.ticker, localCacheThree.ticker);
2497 }
2498
2499
2500
2501
2502
2503
2504
2505 @SuppressWarnings("unchecked")
2506 private static Iterable<CacheBuilder<Object, Object>> allEntryTypeMakers() {
2507 List<CacheBuilder<Object, Object>> result =
2508 newArrayList(allKeyValueStrengthMakers());
2509 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2510 result.add(builder.maximumSize(SMALL_MAX_SIZE));
2511 }
2512 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2513 result.add(builder.expireAfterAccess(99999, SECONDS));
2514 }
2515 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2516 result.add(builder.expireAfterWrite(99999, SECONDS));
2517 }
2518 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2519 result.add(builder.maximumSize(SMALL_MAX_SIZE).expireAfterAccess(99999, SECONDS));
2520 }
2521 for (CacheBuilder<Object, Object> builder : allKeyValueStrengthMakers()) {
2522 result.add(builder.maximumSize(SMALL_MAX_SIZE).expireAfterWrite(99999, SECONDS));
2523 }
2524 return result;
2525 }
2526
2527
2528
2529
2530 @SuppressWarnings("unchecked")
2531 static Iterable<CacheBuilder<Object, Object>> allEvictingMakers() {
2532 return ImmutableList.of(createCacheBuilder().maximumSize(SMALL_MAX_SIZE),
2533 createCacheBuilder().expireAfterAccess(99999, SECONDS),
2534 createCacheBuilder().expireAfterWrite(99999, SECONDS),
2535 createCacheBuilder()
2536 .maximumSize(SMALL_MAX_SIZE)
2537 .expireAfterAccess(SMALL_MAX_SIZE, TimeUnit.SECONDS),
2538 createCacheBuilder()
2539 .maximumSize(SMALL_MAX_SIZE)
2540 .expireAfterWrite(SMALL_MAX_SIZE, TimeUnit.SECONDS));
2541 }
2542
2543
2544
2545
2546 @SuppressWarnings("unchecked")
2547 private static Iterable<CacheBuilder<Object, Object>> allKeyValueStrengthMakers() {
2548 return ImmutableList.of(createCacheBuilder(),
2549 createCacheBuilder().weakValues(),
2550 createCacheBuilder().softValues(),
2551 createCacheBuilder().weakKeys(),
2552 createCacheBuilder().weakKeys().weakValues(),
2553 createCacheBuilder().weakKeys().softValues());
2554 }
2555
2556
2557
2558 private static <K, V> DummyEntry<K, V> createDummyEntry(
2559 K key, int hash, V value, ReferenceEntry<K, V> next) {
2560 DummyEntry<K, V> entry = DummyEntry.create(key, hash, next);
2561 DummyValueReference<K, V> valueRef = DummyValueReference.create(value);
2562 entry.setValueReference(valueRef);
2563 return entry;
2564 }
2565
2566 static class DummyEntry<K, V> implements ReferenceEntry<K, V> {
2567 private K key;
2568 private final int hash;
2569 private final ReferenceEntry<K, V> next;
2570
2571 public DummyEntry(K key, int hash, ReferenceEntry<K, V> next) {
2572 this.key = key;
2573 this.hash = hash;
2574 this.next = next;
2575 }
2576
2577 public static <K, V> DummyEntry<K, V> create(K key, int hash, ReferenceEntry<K, V> next) {
2578 return new DummyEntry<K, V>(key, hash, next);
2579 }
2580
2581 public void clearKey() {
2582 this.key = null;
2583 }
2584
2585 private ValueReference<K, V> valueReference = unset();
2586
2587 @Override
2588 public ValueReference<K, V> getValueReference() {
2589 return valueReference;
2590 }
2591
2592 @Override
2593 public void setValueReference(ValueReference<K, V> valueReference) {
2594 this.valueReference = valueReference;
2595 }
2596
2597 @Override
2598 public ReferenceEntry<K, V> getNext() {
2599 return next;
2600 }
2601
2602 @Override
2603 public int getHash() {
2604 return hash;
2605 }
2606
2607 @Override
2608 public K getKey() {
2609 return key;
2610 }
2611
2612 private long accessTime = Long.MAX_VALUE;
2613
2614 @Override
2615 public long getAccessTime() {
2616 return accessTime;
2617 }
2618
2619 @Override
2620 public void setAccessTime(long time) {
2621 this.accessTime = time;
2622 }
2623
2624 private ReferenceEntry<K, V> nextAccess = nullEntry();
2625
2626 @Override
2627 public ReferenceEntry<K, V> getNextInAccessQueue() {
2628 return nextAccess;
2629 }
2630
2631 @Override
2632 public void setNextInAccessQueue(ReferenceEntry<K, V> next) {
2633 this.nextAccess = next;
2634 }
2635
2636 private ReferenceEntry<K, V> previousAccess = nullEntry();
2637
2638 @Override
2639 public ReferenceEntry<K, V> getPreviousInAccessQueue() {
2640 return previousAccess;
2641 }
2642
2643 @Override
2644 public void setPreviousInAccessQueue(ReferenceEntry<K, V> previous) {
2645 this.previousAccess = previous;
2646 }
2647
2648 private long writeTime = Long.MAX_VALUE;
2649
2650 @Override
2651 public long getWriteTime() {
2652 return writeTime;
2653 }
2654
2655 @Override
2656 public void setWriteTime(long time) {
2657 this.writeTime = time;
2658 }
2659
2660 private ReferenceEntry<K, V> nextWrite = nullEntry();
2661
2662 @Override
2663 public ReferenceEntry<K, V> getNextInWriteQueue() {
2664 return nextWrite;
2665 }
2666
2667 @Override
2668 public void setNextInWriteQueue(ReferenceEntry<K, V> next) {
2669 this.nextWrite = next;
2670 }
2671
2672 private ReferenceEntry<K, V> previousWrite = nullEntry();
2673
2674 @Override
2675 public ReferenceEntry<K, V> getPreviousInWriteQueue() {
2676 return previousWrite;
2677 }
2678
2679 @Override
2680 public void setPreviousInWriteQueue(ReferenceEntry<K, V> previous) {
2681 this.previousWrite = previous;
2682 }
2683 }
2684
2685 static class DummyValueReference<K, V> implements ValueReference<K, V> {
2686 private V value;
2687 boolean loading = false;
2688
2689 public DummyValueReference() {
2690 this.loading = true;
2691 }
2692
2693 public DummyValueReference(V value) {
2694 this.value = value;
2695 }
2696
2697 public static <K, V> DummyValueReference<K, V> create(V value) {
2698 return new DummyValueReference<K, V>(value);
2699 }
2700
2701 public static <K, V> DummyValueReference<K, V> createLoading() {
2702 return new DummyValueReference<K, V>();
2703 }
2704
2705 @Override
2706 public V get() {
2707 return value;
2708 }
2709
2710 @Override
2711 public int getWeight() {
2712 return 1;
2713 }
2714
2715 @Override
2716 public ReferenceEntry<K, V> getEntry() {
2717 return null;
2718 }
2719
2720 @Override
2721 public ValueReference<K, V> copyFor(
2722 ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
2723 return this;
2724 }
2725
2726 public void setLoading(boolean loading) {
2727 this.loading = loading;
2728 }
2729
2730 @Override
2731 public boolean isLoading() {
2732 return loading;
2733 }
2734
2735 @Override
2736 public boolean isActive() {
2737 return !loading;
2738 }
2739
2740 @Override
2741 public V waitForValue() {
2742 return get();
2743 }
2744
2745 @Override
2746 public void notifyNewValue(V newValue) {}
2747
2748 public void clear() {
2749 value = null;
2750 }
2751 }
2752
2753 private static class SerializableCacheLoader
2754 extends CacheLoader<Object, Object> implements Serializable {
2755 @Override
2756 public Object load(Object key) {
2757 return new Object();
2758 }
2759
2760 @Override
2761 public int hashCode() {
2762 return 42;
2763 }
2764
2765 @Override
2766 public boolean equals(Object o) {
2767 return (o instanceof SerializableCacheLoader);
2768 }
2769 }
2770
2771 private static class SerializableRemovalListener<K, V>
2772 implements RemovalListener<K, V>, Serializable {
2773 @Override
2774 public void onRemoval(RemovalNotification<K, V> notification) {}
2775
2776 @Override
2777 public int hashCode() {
2778 return 42;
2779 }
2780
2781 @Override
2782 public boolean equals(Object o) {
2783 return (o instanceof SerializableRemovalListener);
2784 }
2785 }
2786
2787 private static class SerializableTicker extends Ticker implements Serializable {
2788 @Override
2789 public long read() {
2790 return 42;
2791 }
2792
2793 @Override
2794 public int hashCode() {
2795 return 42;
2796 }
2797
2798 @Override
2799 public boolean equals(Object o) {
2800 return (o instanceof SerializableTicker);
2801 }
2802 }
2803
2804 private static class SerializableWeigher<K, V> implements Weigher<K, V>, Serializable {
2805 @Override
2806 public int weigh(K key, V value) {
2807 return 42;
2808 }
2809
2810 @Override
2811 public int hashCode() {
2812 return 42;
2813 }
2814
2815 @Override
2816 public boolean equals(Object o) {
2817 return (o instanceof SerializableWeigher);
2818 }
2819 }
2820
2821 }